/*
 * @Author: 缄默
 * @Date: 2022-04-13 14:48:25
 * @LastEditors: 缄默
 * @LastEditTime: 2022-04-13 15:15:14
 */

//快排实现

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& arr);
void QSort(vector<int>& arr, int left, int right);

int main() {
    vector<int> arr({3, 1, 2, 2, 6, 8});
    quickSort(arr);
    for (auto i : arr) {
        cout << i << " ";
    }
    return 0;
}

void quickSort(vector<int>& arr) {
    if (arr.size() == 0) return ;
    QSort(arr, 0, arr.size() - 1);
}

void QSort(vector<int>& arr, int left, int right) {
    int low = left;
    int high = right;
    int povit = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= povit) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= povit) low++;
        arr[high] = arr[low];
    }
    arr[low] = povit;
    if (left < low) {
        QSort(arr,left, low - 1);
    }
    if (right > low) {
        QSort(arr, low + 1, right);
    }
}